package day_2023_7_to_10;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author haomin
 * @date 2023/07/20 23:36
 **/
public class Day_7_20 {
    class Solution {
        public ListNode deleteNode(ListNode head, int val) {
            if (head == null) return head;
            ListNode dummyHead = new ListNode(-1);
            dummyHead.next = head;
            ListNode cur = dummyHead;
            while(cur.next != null && cur.next.val != val)
                cur = cur.next;
            if (cur.next != null) cur.next = cur.next.next;
            return dummyHead.next;
        }
    }
    class Solution2 {
        public ListNode getKthFromEnd(ListNode head, int k) {
            Deque<ListNode> s = new LinkedList<>();
            while(head != null) {
                s.push(head);
                head = head.next;
            }
            while(k-- > 1) s.pop();
            return s.pop();
        }
    }
    class Solution3 {
        public ListNode getKthFromEnd(ListNode head, int k) {
            ListNode n1 = head;
            ListNode n2 = head;
            while(k-- > 0) n1 = n1.next;
            while(n1 != null) {
                n1 = n1.next;
                n2 = n2.next;
            }
            return n2;
        }
    }
    class Solution4 {
        public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
            if(l1 == null) return l2;
            if(l2 == null) return l1;
            if(l1.val < l2.val) {
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            }else {
                l2.next = mergeTwoLists(l1, l2.next);
                return l2;
            }
        }
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if(l1 == null) return l2;
            if(l2 == null) return l1;
            ListNode dummyHead = new ListNode(-1);
            ListNode cur = dummyHead;
            while(l1 != null && l2 != null) {
                if(l1.val < l2.val) {
                    cur.next = l1;
                    l1 = l1.next;
                }else {
                    cur.next = l2;
                    l2 = l2.next;
                }
                cur = cur.next;
            }
            if(l1 != null) cur.next = l1;
            if(l2 != null) cur.next = l2;
            return dummyHead.next;
        }
    }
    class Solution5 {
        ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            ListNode n1 = headA;
            ListNode n2 = headB;
            while(n1 != n2) {
                n1 = n1 == null ? headB : n1.next;
                n2 = n2 == null ? headA : n2.next;
            }
            return n1;
        }
    }
}